package own.stu.jobgib.playown.alg.solution.sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class QuickSort {
    public static void main(String[] args) {

         int[] nums = new int[]{3, 2, 1, 5, 6, 4};
//        int[] nums = new int[]{2, 1, 5, 6, 4};
        System.out.println(Arrays.stream(nums).boxed().collect(Collectors.toList()));
        sort(nums);
        System.out.println(Arrays.stream(nums).boxed().collect(Collectors.toList()));
    }

    public static void sort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        int n = nums.length;

        sort(nums, 0, n - 1);
    }

    private static void sort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = quickSelect(nums, l, r);
        sort(nums, 0, p - 1);
        sort(nums, p + 1, r);
    }

    private static int quickSelect(int[] nums, int l, int r) {
        int p = nums[r];
        int i = l - 1;
        for (int j = l; j < r; j++) {
            if (nums[j] <= p) {
                i += 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
